#ifndef __JIENING_BTREE_HEAD__
#define __JIENING_BTREE_HEAD__

#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>

using namespace std;

/*
B-树是一种多路搜索树（并不是二叉的）：
1. 定义任意非叶子结点最多只有M个儿子；且M>2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；
5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8. 所有叶子结点位于同一层；
9. 由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；
10. 删除结点时，需将两个不足M/2的兄弟结点合并；
*/

/*
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；
重复，直到所对应的儿子指针为空，或已经是叶子结点；
B-树的特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率
所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；
*/

// BTRKT 关键字类型
// BTRVT 关键字对应的列表中的元素的类型
template<class BTRKT, class BTRVT>
struct jieningBtreeKVpair
{
	BTRKT thekey;
	BTRVT* thev;
	jieningBtreeKVpair(BTRKT keyval, BTRVT* vallist){thekey = keyval; thev=vallist;}
	jieningBtreeKVpair(BTRKT keyval){thekey = keyval; thev=NULL;}
	jieningBtreeKVpair(){thev=NULL;}
	~jieningBtreeKVpair()
	{
		//cout<<"in jieningBtreeKVpair::~jieningBtreeKVpair"<<endl;
		if(NULL != thev){delete thev; thev=NULL;}
	}
};

template<class BTRKT, class BTRVT>
class jieningBtree
{
public:
	// 构造函数theM>2
	jieningBtree(unsigned int theM);

	// 添加节点到Btree,root node
	bool addKvp(struct jieningBtreeKVpair<BTRKT, BTRVT>* kvInsert);

	// 添加节点到Btree,root node
	bool addKvp(const BTRKT& keyval);

	// 打印整个Btree的结构
	void doPrint(int level=0);

	// 在本节点的kv列表上的折半查找逻辑
	// equalpos: 返回和keyval相等的key的下标，如果没有相等的返回-1
	// insertpos: 返回keyval应该被插入的位置，如果找到有key和keyval相等，返回-1
	void findkey(const BTRKT& keyval, int& equalpos, int& insertpos);

	// 如果在以该节点为根的子树上找到有和keyval相同的值返回kvpair；没有找到返回NULL
	struct jieningBtreeKVpair<BTRKT, BTRVT>* findKeyPos(const BTRKT& keyval, char* pathinf=NULL);

	// 如果在以该节点为根的子树上找到有和keyval相同的值, 从树上取出kvp，返回之，没有找到返回NULL
	struct jieningBtreeKVpair<BTRKT, BTRVT>* findToDeleteKV(const BTRKT& keyval, char* pathinf=NULL);

	// 找寻并返回树中key值最小的kvp
	struct jieningBtreeKVpair<BTRKT, BTRVT>* findMinKvp();

	// 找寻并返回树中key值最大的kvp
	struct jieningBtreeKVpair<BTRKT, BTRVT>* findMaxKvp();

	// 以该节点为根的子树所有的关键字的个数之和
	unsigned getKeyCount();

	// 返回树中kvp的数量
	unsigned getKeyListLen(){return this->m_keyNum;}

	// 返回树是否是叶子节点
	bool isLeafNode(){return this->m_isLeaf;}

	// 检查树是否满足成为Btree的各种条件
	bool doTreeCheck();

	// 析构函数
	~jieningBtree();

protected:

	// 检查树是否满足成为Btree的各种条件,用于递归调用
	// isRoot：是否是从根节点开始检查
	// lp：该节点的左边的父kvp指针，如果没有设置为NULL，用于检查本节点kvp的key值是否比lp指向的大
	// rp：该节点的右边的父kvp指针，如果没有设置为NULL，用于检查本节点kvp的key值是否比rp指向的小
	// leaflevel：叶节点所在层次，初始值为-1，用于检查叶节点是否都处于同一层、
	// nowlevel：标示节点当前所在的层，0 base
	bool doTreeCheck(bool isRoot, jieningBtreeKVpair<BTRKT, BTRVT>* lp, jieningBtreeKVpair<BTRKT, BTRVT>* rp, int& leaflevel, int nowlevel);

	// 节点分裂逻辑，分裂的结果是产生一个新的节点，和一个分开新旧节点的kvp
	// splitnode：分裂出的新节点的指针，里面包含着较大的kvp
	// kvtoadd：一个分开新旧节点的kvp
	bool splitSelfNode(struct jieningBtreeKVpair<BTRKT, BTRVT>*& kvtoadd, jieningBtree*& splitnode);

	// 以当前节点为根的子树中，将key最小的（位于最左边的叶子节点的第一个元素)kv对摘出，如果摘出导致子节点需要合并，合并之
	struct jieningBtreeKVpair<BTRKT, BTRVT>* findtoDeleteMinKvp();

	// 以当前节点为根的子树中，将key最大的（位于最右边的叶子节点的最后一个元素)kv对摘出，如果摘出导致子节点需要合并，合并之
	struct jieningBtreeKVpair<BTRKT, BTRVT>* findtoDeleteMaxKvp();

	// 在非叶节点上，第mergepos个子节点 因为关键字减少需要合并
	bool doMegerChild(int mergepos);

	// 添加节点到Btree，如果因为kvlist的长度超过M-1,节点分裂，
	// addParentKV：带回分裂后的中值
	// splitNode：指向分裂后的节点, 调用该函数的逻辑负责将splitNode添加到树中
	bool addKvp(struct jieningBtreeKVpair<BTRKT, BTRVT>* insertKV, struct jieningBtreeKVpair<BTRKT, BTRVT>*& addParentKV, jieningBtree*& splitNode);

	// 如果在以该节点为根的子树上找到有和keyval相同的值, 从树上删除找到的kvpair返回true；没有找到返回false
	// 如果成功删除节点导致keynum<M/2-1,needMerge设置为true，调用该函数的逻辑负责调整keynum
	struct jieningBtreeKVpair<BTRKT, BTRVT>* findToDeleteKV(const BTRKT& keyval, bool& needMerge);

	//===================================member variaties ===============================
	// 非叶子节点可以拥有的最大的子节点数
	const unsigned m_maxChildNum;

	// 节点实际拥有的kvp个数
	unsigned m_keyNum;

	// 存放kvp指针的数组, m_maxChildNum/2-1 <= list_size = m_keyNum <= m_maxChildNum-1
	struct jieningBtreeKVpair<BTRKT, BTRVT>** m_kvlist;

	// 存放子节点指针的数组, list_size=m_keyNum+1<=m_maxChildNum
	jieningBtree** m_childlist;

	// 标识节点是否是叶子节点
	bool m_isLeaf;
};

//=======================================================================================
//=======================================================================================
//=======================================================================================

// 构造函数theM>2
template<class BTRKT, class BTRVT>
jieningBtree<BTRKT, BTRVT>::jieningBtree(unsigned int theM):
m_maxChildNum(theM>2?theM:3)
{
	//cout<<((long)this)<<" in jieningBtree::jieningBtree"<<endl;
	this->m_keyNum = 0;
	this->m_childlist = new jieningBtree<BTRKT, BTRVT>*[this->m_maxChildNum+1];	//(jieningBtree**)malloc(this->m_maxChildNum*sizeof(jieningBtree*));
	this->m_kvlist = new struct jieningBtreeKVpair<BTRKT, BTRVT>*[this->m_maxChildNum];
	//this->m_keylist = new BTRKT[this->m_maxChildNum];				//(int*)malloc(this->m_maxChildNum*sizeof(int));
	//this->m_doclistarr = new BTRVT*[this->m_maxChildNum];				//(int*)malloc(this->m_maxChildNum*sizeof(int));
	for(unsigned int loop=0; loop<this->m_maxChildNum; ++loop)
	{
		this->m_childlist[loop] = NULL;
		//this->m_doclistarr[loop] = NULL;
		this->m_kvlist[loop] = NULL;
	}
	this->m_childlist[this->m_maxChildNum] = NULL;
	this->m_isLeaf = true;
}

// 添加节点到Btree,root node
template<class BTRKT, class BTRVT>
bool jieningBtree<BTRKT, BTRVT>::addKvp(const BTRKT& keyval)
{
	return this->addKvp(new struct jieningBtreeKVpair<BTRKT, BTRVT>(keyval));
}

// 添加节点到Btree的root node
template<class BTRKT, class BTRVT>
bool jieningBtree<BTRKT, BTRVT>::addKvp(struct jieningBtreeKVpair<BTRKT, BTRVT>* kvInsert)
{
	//cout<<"in jieningBtree::addKvp short,keyval="<<keyval<<" this->m_keyNum="<<this->m_keyNum<<endl;

	struct jieningBtreeKVpair<BTRKT, BTRVT>* kvtoadd = NULL;
	jieningBtree* childtoadd=NULL;
	if(!this->addKvp(kvInsert, kvtoadd, childtoadd))
	{
		return false;
	}
	//cout<<"in jieningBtree::addKvp short, this->m_keyNum="<<this->m_keyNum<<endl;

	if(NULL != childtoadd)
	{
		//cout<<"in jieningBtree::addKvp short, valtoadd="<<valtoadd<<" "<<endl;
		// 拷贝root节点内容到左节点
		//cout<<((long)this)<<" in jieningBtree::addKvp short before new node"<<endl;
		jieningBtree* leftnode = new jieningBtree(this->m_maxChildNum);
		leftnode->m_isLeaf = this->m_isLeaf;
		for(unsigned int loop=0; loop < this->m_maxChildNum; ++loop)
		{
			if(loop < this->m_keyNum)
			{
				//leftnode->m_keylist[loop] = this->m_keylist[loop];
				//leftnode->m_doclistarr[loop] = this->m_doclistarr[loop];
				leftnode->m_kvlist[loop] = this->m_kvlist[loop];
			}
			if(loop <= this->m_keyNum)
			{
				leftnode->m_childlist[loop] = this->m_childlist[loop];
			}
			this->m_kvlist[loop] = NULL;
			this->m_childlist[loop] = NULL;
		}
		//leftnode->m_childlist[this->m_keyNum] = this->m_childlist[this->m_keyNum];
		leftnode->m_keyNum = this->m_keyNum;
		//this->m_childlist[this->m_keyNum] = NULL;

		// root节点变成非叶节点
		//this->m_keylist[0] = valtoadd;
		this->m_kvlist[0] = kvtoadd;
		this->m_keyNum = 1;
		this->m_childlist[0] = leftnode;
		this->m_childlist[1] = childtoadd;
		this->m_isLeaf = false;
	}
	return true;
}

// 节点分裂
template<class BTRKT, class BTRVT>
bool jieningBtree<BTRKT, BTRVT>::splitSelfNode(
	struct jieningBtreeKVpair<BTRKT, BTRVT>*& kvtoadd,
	jieningBtree*& splitnode)
{
	if(this->m_keyNum <= (this->m_maxChildNum - 1))
	{
		return false;
	}
	// key列表已经满载的处理逻辑
	// 分裂成两个叶节点，以下标为M/2的元素为界，当前节点保留M/2前面的元素
	// 分裂出的新叶子节点保留M/2后面的元素
	// kvtoadd 和 splitnode 返回给父节点做插入

	unsigned int breakpos = this->m_keyNum/2;
	kvtoadd = this->m_kvlist[breakpos];
	this->m_kvlist[breakpos]  = NULL;
	//cout<<"node full, breakpos="<<breakpos<<", breakval="<<breakval<<endl;

	//cout<<((long)this)<<" in jieningBtree::splitSelfNode"<<endl;
	splitnode = new jieningBtree(this->m_maxChildNum);
	splitnode->m_isLeaf = this->m_isLeaf;
	unsigned int wcout = 0;
	for(unsigned int loop = breakpos+1; loop < this->m_keyNum; ++loop)
	{
		splitnode->m_kvlist[wcout] = this->m_kvlist[loop];
		this->m_kvlist[loop]  =NULL;
		if(!this->m_isLeaf)
		{
			splitnode->m_childlist[wcout] = this->m_childlist[loop];
			this->m_childlist[loop] = NULL;
		}
		splitnode->m_keyNum += 1;
		++wcout;
	}
	if(!this->m_isLeaf)
	{
		splitnode->m_childlist[wcout] = this->m_childlist[this->m_keyNum];
		this->m_childlist[this->m_keyNum] = NULL;
	}

	this->m_keyNum = (this->m_keyNum/2);
	return true;
}

// 添加节点到Btree
template<class BTRKT, class BTRVT>
bool jieningBtree<BTRKT, BTRVT>::addKvp(
	struct jieningBtreeKVpair<BTRKT, BTRVT>* kvInsert,
	struct jieningBtreeKVpair<BTRKT, BTRVT>*& kvtoadd,
	jieningBtree*& splitnode)
{
	//折半查找keyval该插入的位置insertpos
	int insertpos = -1;
	int equalpos = -1;
	this->findkey(kvInsert->thekey, equalpos, insertpos);
	if(0>insertpos)
	{
		//cout<<"find keyval "<<keyval<<" already int keylist"<<endl;
		return false;
	}

	if(this->m_isLeaf)
	{
		//如果是叶节点，key列表还可以插入，
		//keyval该插入的位置为insertpos，移动insertpos之后的元素
		//cout<<"insertpos="<<insertpos<<endl;
		for(int loop=this->m_keyNum; loop > insertpos; --loop)
		{
			this->m_kvlist[loop] = this->m_kvlist[loop-1];
			//this->m_keylist[loop] = this->m_keylist[loop-1];
			//this->m_doclistarr[loop] = this->m_doclistarr[loop-1];
		}
		this->m_kvlist[insertpos] = kvInsert;
		this->m_keyNum += 1;

		if(this->m_keyNum > (this->m_maxChildNum - 1))
		{
			this->splitSelfNode(kvtoadd, splitnode);
		}
	}
	else
	{
		//如果是非叶节点，查找key列表，找到应该被插入的子节点，在子节点上递归调用该函数。
		jieningBtree* keyAddNode = this->m_childlist[insertpos];
		if(NULL == keyAddNode)
		{
			return false;
		}

		struct jieningBtreeKVpair<BTRKT, BTRVT>* breakPoint = NULL;
		jieningBtree* breakNode = NULL;
		if(!keyAddNode->addKvp(kvInsert, breakPoint, breakNode))
		{
			return false;
		}

		if(NULL != breakNode)
		{
			//keyval该插入的位置为insertpos，移动insertpos之后的元素
			cout<<"insertpos="<<insertpos<<endl;
			for(int loop=this->m_keyNum; loop > insertpos; --loop)
			{
				//this->m_keylist[loop] = this->m_keylist[loop-1];
				//this->m_doclistarr[loop] = this->m_doclistarr[loop-1];
				this->m_kvlist[loop] = this->m_kvlist[loop-1];
				this->m_childlist[loop+1] = this->m_childlist[loop];
			}
			//this->m_keylist[insertpos] = valtoadd;
			//this->m_doclistarr[insertpos] = ;
			this->m_kvlist[insertpos] = breakPoint;
			this->m_childlist[insertpos+1] = breakNode;
			this->m_keyNum += 1;

			if(this->m_keyNum > (this->m_maxChildNum - 1))
			{
				this->splitSelfNode(kvtoadd, splitnode);
			}
		}
	}

	return true;
}

// 打印整个Btree的结构
template<class BTRKT, class BTRVT>
void jieningBtree<BTRKT, BTRVT>::doPrint(int level)
{
	if(0 == level)
	{
		cout<<endl<<"======================jieningBtree::doPrint begin ========================="<<endl;
	}
	if(this->m_isLeaf)
	{
		for(int k=0;k<level;++k)
		{
			cout<<"\t";
		}
		cout<<"[[[[[[[[[[[[[[[[[[[["<<endl;
	}

	for(unsigned int loop=0; loop < this->m_keyNum; ++loop)
	{
		if(NULL != this->m_childlist[loop])
		{
			this->m_childlist[loop]->doPrint(level+1);
		}
		for(int k=0;k<level;++k)
		{
			cout<<"\t";
		}
		if(0 == loop)
		{
			cout<<"this->"<<((long)this)<<", "<<this->m_keyNum<<" keys, ";
			if(this->m_isLeaf)
			{
				cout<<"leaf node"<<endl;
			}
			else
			{
				cout<<(this->m_keyNum+1)<<" child nodes"<<endl;
			}
			for(int k=0;k<level;++k)
			{
				cout<<"\t";
			}
		}
		cout<<"key["<<loop<<"]="<<this->m_kvlist[loop]->thekey<<endl;
	}
	if(NULL != this->m_childlist[this->m_keyNum])
	{
		this->m_childlist[this->m_keyNum]->doPrint(level+1);
	}

	if(this->m_isLeaf)
	{
		for(int k=0;k<level;++k)
		{
			cout<<"\t";
		}
		cout<<"]]]]]]]]]]]]]]]]]]]]"<<endl;
	}
	if(0 == level)
	{
		cout<<endl<<"======================jieningBtree::doPrint end ========================="<<endl;
	}
}

template<class BTRKT, class BTRVT>
struct jieningBtreeKVpair<BTRKT, BTRVT>* jieningBtree<BTRKT, BTRVT>::findKeyPos(const BTRKT& keyval, char* pathinf)
{
	cout << "in jieningBtree::findKeyPos try to find keyval=" << keyval << endl;

	int insertpos = -1;
	int equalpos = -1;
	this->findkey(keyval, equalpos, insertpos);

	if(0 <= equalpos)
	{
		if (pathinf != NULL)
		{
			sprintf(pathinf, "%s -> %d", pathinf, equalpos);
		}
		return this->m_kvlist[equalpos];
	}
	if (pathinf != NULL)
	{
		sprintf(pathinf, "%s -> %d", pathinf, insertpos);
	}

	if (this->m_isLeaf)
	{
		return NULL;
	}
	else
	{
		if(0<=insertpos && NULL != this->m_childlist[insertpos])
		{
			return this->m_childlist[insertpos]->findKeyPos(keyval, pathinf);
		}
	}

	return NULL;
}

// 以该节点为根的子树所有的关键字的个数之和
template<class BTRKT, class BTRVT>
unsigned jieningBtree<BTRKT, BTRVT>::getKeyCount()
{
	int countnum = this->m_keyNum;
	if(!this->m_isLeaf)
	{
		for(unsigned int loop = 0; loop<=this->m_keyNum; ++loop)
		{
			countnum += this->m_childlist[loop]->getKeyCount();
		}
	}
	return countnum;
}

// 在本节点的kv列表上的折半查找逻辑
// equalpos: 返回和keyval相等的key的下标，如果没有相等的返回-1
// insertpos: 返回keyval应该被插入的位置，如果找到有key和keyval相等，返回-1
template<class BTRKT, class BTRVT>
void jieningBtree<BTRKT, BTRVT>::findkey(const BTRKT& keyval, int& equalpos, int& insertpos)
{
	//如果是叶节点，key列表还可以插入的处理逻辑
	if (this->m_keyNum == 0)
	{
		equalpos = -1;
		insertpos = 0;
		return;
	}

	// 折半查找keyval该插入的位置insertpos
	int frompos = 0;
	int endpos = (this->m_keyNum - 1);
	int midpos;

	while (true)
	{
		if (this->m_kvlist[frompos]->thekey == keyval)
		{
			equalpos = frompos;
			insertpos = -1;
			return;
		}
		else if (this->m_kvlist[endpos]->thekey == keyval)
		{
			equalpos = endpos;
			insertpos = -1;
			return;
		}
		else if (keyval < this->m_kvlist[frompos]->thekey)
		{
			equalpos = -1;
			insertpos = frompos;
			return;
		}
		else if (this->m_kvlist[endpos]->thekey < keyval)
		{
			equalpos = -1;
			insertpos = endpos + 1;
			return;
		}
		else
		{
			midpos = (frompos + endpos) / 2;
			cout << "keyval=" << keyval << "\tfrompos=" << frompos
					<< "\tendpos=" << endpos << "\tmidpos=" << midpos << endl;
			if (this->m_kvlist[midpos]->thekey == keyval)
			{
				//如果在m_keylis中找到和keyval相等的值
				equalpos = midpos;
				insertpos = -1;
				return;
			}
			else if (this->m_kvlist[midpos]->thekey < keyval)
			{
				//如果中间点值比keyval小，起点设置为中间点
				insertpos = midpos + 1;
				frompos = midpos;
			}
			else
			{
				//如果中间点值比keyval大，终点设置为中间点
				insertpos = midpos;
				endpos = midpos;
			}

			if (1 >= (endpos - frompos))
			{
				//起点和终点之间已经没有别的点
				break;
			}
		}
	}

	equalpos = -1;
	insertpos = insertpos;
	return;
}

// 如果在以该节点为根的子树上找到有和keyval相同的值, 从树上删除找到的kvpair返回true；没有找到返回false
// 如果成功删除节点导致keynum<M/2-1,needMerge设置为true，调用该函数的逻辑负责调整keynum
template<class BTRKT, class BTRVT>
struct jieningBtreeKVpair<BTRKT, BTRVT>* jieningBtree<BTRKT, BTRVT>::findToDeleteKV(const BTRKT& keyval, bool& needMerge)
{
	needMerge = false;
	struct jieningBtreeKVpair<BTRKT, BTRVT>* rtnkvp = NULL;

	int insertpos=-1;
	int equalpos=-1;
	this->findkey(keyval, equalpos, insertpos);

	if(0 > equalpos)
	{
		// 在kvlist中没有找到keyval
		if(this->m_isLeaf)
		{
			return NULL;
		}

		//向下递归寻找关键字
		if(0<=insertpos && insertpos<=(int)this->m_keyNum && NULL != this->m_childlist[insertpos])
		{
			bool needAdjust = false;
			rtnkvp = this->m_childlist[insertpos]->findToDeleteKV(keyval, needAdjust);
			if(NULL == rtnkvp)
			{
				return NULL;
			}

			// 子节点中找到关键字，并在子节点上删除成功
			if(needAdjust)
			{
				//子节点删除成功后，关键子个数小于M/2-1，需要调整
				this->doMegerChild(insertpos);
				if((this->m_maxChildNum/2-1) > (this->m_keyNum))
				{
					// 调整后，导致关键字数小于M/2-1
					needMerge = true;
				}
			}
			return rtnkvp;
		}
		return NULL;
	}

	// 如果在本节点找到要删除的关键字
	if(this->m_isLeaf)
	{
		// 如果是叶节点
		if(NULL != this->m_kvlist[equalpos])
		{
			rtnkvp = this->m_kvlist[equalpos];
			this->m_kvlist[equalpos] = NULL;
		}

		for(unsigned int loop=equalpos; loop<(this->m_keyNum-1); ++loop)
		{
			this->m_kvlist[loop] = this->m_kvlist[loop+1];
		}
		this->m_kvlist[this->m_keyNum-1] = NULL;
		this->m_keyNum -= 1;

		if((this->m_maxChildNum/2-1) > (this->m_keyNum))
		{
			// 删去一个kv对后，节点的kv数还是小于M/2-1, 设置needMerge为true，通知父节点合并相邻节点
			needMerge = true;
		}
		return rtnkvp;
	}
	else
	{
		// 如果是非叶节点
		if(this->m_childlist[equalpos]->m_keyNum >= this->m_childlist[equalpos+1]->m_keyNum)
		{
			// 左子树的kvp较多，摘下整个子树中key值最大的kvp
			struct jieningBtreeKVpair<BTRKT, BTRVT>* maxkvp = this->m_childlist[equalpos]->findtoDeleteMaxKvp();

			// 摘下的kvp替换equalpos处的用于返回的kvp
			if(NULL == maxkvp)
			{
				return NULL;
			}
			rtnkvp = this->m_kvlist[equalpos];
			this->m_kvlist[equalpos] = maxkvp;

			// 如果左子树的kvp数量不足调整之
			if(this->m_childlist[equalpos]->m_keyNum < (this->m_maxChildNum/2 - 1))
			{
				if(!this->doMegerChild(equalpos))
				{
					return NULL;
				}
				if(this->m_keyNum < (this->m_maxChildNum/2 - 1))
				{
					needMerge = true;
				}
			}
			return rtnkvp;
		}
		else
		{
			// 右子树的kvp较多，摘下整个子树中key值最小的kvp
			struct jieningBtreeKVpair<BTRKT, BTRVT>* minkvp = this->m_childlist[equalpos+1]->findtoDeleteMinKvp();

			// 摘下的kvp替换equalpos处的用于返回的kvp
			if(NULL == minkvp)
			{
				return NULL;
			}
			rtnkvp = this->m_kvlist[equalpos];
			this->m_kvlist[equalpos] = minkvp;

			// 如果右子树的kvp数量不足调整之
			if(this->m_childlist[equalpos+1]->m_keyNum < (this->m_maxChildNum/2 - 1))
			{
				if(!this->doMegerChild(equalpos+1))
				{
					return NULL;
				}
				if(this->m_keyNum < (this->m_maxChildNum/2 - 1))
				{
					needMerge = true;
				}
			}
			return rtnkvp;
		}
	}

	return NULL;
}

template<class BTRKT, class BTRVT>
struct jieningBtreeKVpair<BTRKT, BTRVT>* jieningBtree<BTRKT, BTRVT>::findtoDeleteMinKvp()
{
	struct jieningBtreeKVpair<BTRKT, BTRVT>* rtnkvp = NULL;
	if(this->m_isLeaf)
	{
		rtnkvp = this->m_kvlist[0];
		for(unsigned int loop=0; loop<this->m_keyNum-1; ++loop)
		{
			this->m_kvlist[loop] = this->m_kvlist[loop+1];
		}
		this->m_kvlist[this->m_keyNum-1] = NULL;
		this->m_keyNum -= 1;
		return rtnkvp;
	}

	rtnkvp = this->m_childlist[0]->findtoDeleteMinKvp();
	if(NULL != rtnkvp)
	{
		if(this->m_childlist[0]->m_keyNum < (this->m_maxChildNum/2 - 1))
		{
			this->doMegerChild(0);
		}
		return rtnkvp;
	}
	return NULL;
}

template<class BTRKT, class BTRVT>
struct jieningBtreeKVpair<BTRKT, BTRVT>* jieningBtree<BTRKT, BTRVT>::findtoDeleteMaxKvp()
{
	struct jieningBtreeKVpair<BTRKT, BTRVT>* rtnkvp = NULL;
	if(this->m_isLeaf)
	{
		rtnkvp = this->m_kvlist[this->m_keyNum-1];
		this->m_kvlist[this->m_keyNum-1] = NULL;
		this->m_keyNum -= 1;
		return rtnkvp;
	}

	rtnkvp = this->m_childlist[this->m_keyNum]->findtoDeleteMaxKvp();
	if(NULL != rtnkvp)
	{
		if(this->m_childlist[this->m_keyNum]->m_keyNum < (this->m_maxChildNum/2 - 1))
		{
			this->doMegerChild(this->m_keyNum);
		}
		return rtnkvp;
	}
	return NULL;
}

// 在非叶节点上，第mergepos个子节点 因为关键字减少需要合并
template<class BTRKT, class BTRVT>
bool jieningBtree<BTRKT, BTRVT>::doMegerChild(int mergepos)
{
	if(this->m_isLeaf)
	{
		return false;
	}
	if(mergepos<0 || (int)this->m_keyNum < mergepos)
	{
		return false;
	}

	// 寻找另一个合并对象的下标mergechild
	int mergechild = -1;

	if(0<=(mergepos-1))
	{
		if(this->m_childlist[mergepos-1]->m_keyNum > (this->m_maxChildNum/2 - 1))
		{
			mergechild = mergepos-1;
		}
	}
	if(-1 == mergechild)
	{
		if((int)this->m_keyNum >= (mergepos+1))
		{
			if(this->m_childlist[mergepos+1]->m_keyNum > (this->m_maxChildNum/2 - 1))
			{
				mergechild = mergepos+1;
			}
		}
	}
	if(-1 == mergechild)
	{
		mergechild = (0<=(mergepos-1)) ? (mergepos-1) : (mergepos+1);
	}

	// 确定左右子节点
	int leftchild = mergepos < mergechild ? mergepos : mergechild;
	int rightchild = mergepos > mergechild ? mergepos : mergechild;

	jieningBtree<BTRKT, BTRVT>* leftp = this->m_childlist[leftchild];
	jieningBtree<BTRKT, BTRVT>* rightp = this->m_childlist[rightchild];

	// mergeKeyNum = 待合并的两个子节点的关键字数目之和，和这两个关键字之间的父节点上的关键字
	int mergeKeyNum = leftp->m_keyNum + rightp->m_keyNum + 1;

	if(mergeKeyNum <= (int)(this->m_maxChildNum-1))
	{
		// 待合并的两个子节点可以合并成一个子节点，并且父节点减少一个关键字

		// 父节点关键字移入左子节点
		leftp->m_kvlist[leftp->m_keyNum] = this->m_kvlist[leftchild];

		// 右子节点移入左子节点
		for(int loop=0;loop < (int)rightp->m_keyNum;++loop)
		{
			leftp->m_kvlist[leftp->m_keyNum + 1 + loop] = rightp->m_kvlist[loop];
			rightp->m_kvlist[loop] = NULL;
		}
		if(!rightp->m_isLeaf)
		{
			//右子节点中的子节点移入左节点
			for(int loop=0;loop <= (int)rightp->m_keyNum;++loop)
			{
				leftp->m_childlist[leftp->m_keyNum + 1 + loop] = rightp->m_childlist[loop];
				rightp->m_childlist[loop] = NULL;
			}
		}
		// 修改左子节点的关键字数目
		leftp->m_keyNum = mergeKeyNum;

		// 删除父节点关键字
		for(int loop=leftchild; loop < (int)this->m_keyNum-1; ++loop)
		{
			this->m_kvlist[loop] = this->m_kvlist[loop+1];
		}
		this->m_kvlist[this->m_keyNum-1] = NULL;
		// 删除右子节点
		for(int loop=rightchild; loop < (int)this->m_keyNum; ++loop)
		{
			this->m_childlist[loop] = this->m_childlist[loop+1];
		}
		this->m_childlist[this->m_keyNum]=NULL;

		this->m_keyNum -= 1;
	}
	else
	{
		/*
		//待合并的两个子节点，连同两个关键字之间的父节点上的关键字合成一个大的节点, 然后在平分或是合并
		jieningBtree** tmp_childlist = new jieningBtree*[mergeKeyNum];
		struct jieningBtreeKVpair<BTRKT, BTRVT>** tmp_kvlist = new struct jieningBtreeKVpair<BTRKT, BTRVT>*[mergeKeyNum+1];
		for(unsigned int loop=0;loop < leftp->m_keyNum; ++loop)
		{
			tmp_kvlist[loop] = leftp->m_kvlist[loop];
			tmp_childlist[loop] = leftp->m_childlist[loop];
		}
		tmp_childlist[leftp->m_keyNum] = leftp->m_childlist[leftp->m_keyNum];

		tmp_kvlist[leftp->m_keyNum] = this->m_kvlist[leftchild];
		for(unsigned int loop=0;loop < rightp->m_keyNum; ++loop)
		{
			tmp_kvlist[leftp->m_keyNum+1+loop] = rightp->m_kvlist[loop];
			tmp_childlist[leftp->m_keyNum+1+loop] = rightp->m_childlist[loop];
		}
		tmp_childlist[leftp->m_keyNum+rightp->m_keyNum+1] = rightp->m_childlist[rightp->m_keyNum];
		*/

		// 待合并的两个子节点的关键字平均分配之，两个子节点之间的父节点的关键字被替换
		if((int)leftp->m_keyNum < mergeKeyNum/2)
		{
			// 左子节点的关键字较少

			// 需要从右节点移出的关键字数目，其中有kvpMoveFromRight-1将移动到左节点
			int kvpMoveFromRight = mergeKeyNum/2 - leftp->m_keyNum;

			// 父节点关键字移入左节点
			leftp->m_kvlist[leftp->m_keyNum] = this->m_kvlist[leftchild];

			// 右子节点kvpMoveFromRight-1个关键字移入左节点
			for(int loop=0; loop<kvpMoveFromRight-1; ++loop)
			{
				leftp->m_kvlist[leftp->m_keyNum+1+loop] = rightp->m_kvlist[loop];
			}

			// 右节点第kvpMoveFromRight个kv移入父节点
			this->m_kvlist[leftchild] = rightp->m_kvlist[kvpMoveFromRight-1];

			// 右子节点减少kvpMoveFromRight个关键字
			for(int loop=0; loop < (int)rightp->m_keyNum; ++loop)
			{
				if(loop < ((int)rightp->m_keyNum - kvpMoveFromRight))
				{
					rightp->m_kvlist[loop] = rightp->m_kvlist[loop + kvpMoveFromRight];
				}
				else
				{
					rightp->m_kvlist[loop] = NULL;
				}
			}

			if(!rightp->m_isLeaf)
			{
				//如果子节点不是叶子节点

				//从右子节点移出kvpMoveFromRight个子节点到左节点
				for(int loop=0; loop<kvpMoveFromRight; ++loop)
				{
					leftp->m_childlist[leftp->m_keyNum+1+loop] = rightp->m_childlist[loop];
				}

				// 右子节点减少kvpMoveFromRight个子节点
				for(int loop=0; loop <= (int)rightp->m_keyNum; ++loop)
				{
					if(loop < ((int)rightp->m_keyNum - kvpMoveFromRight))
					{
						rightp->m_childlist[loop] = rightp->m_childlist[loop + kvpMoveFromRight];
					}
					else
					{
						rightp->m_childlist[loop] = NULL;
					}
				}
			}

			//更改左右子节点的关键数
			leftp->m_keyNum = mergeKeyNum/2;
			rightp->m_keyNum = rightp->m_keyNum - kvpMoveFromRight;
		}
		else if((int)leftp->m_keyNum > mergeKeyNum/2)
		{
			//左子节点的关键字较多

			// 需要从左节点移动关键字到右节点的数目
			int kvpMoveFromLeft = leftp->m_keyNum - mergeKeyNum/2;

			// 右节点准备加入kvpMoveFromLeft个关键字
			for(int loop = rightp->m_keyNum-1; loop>=0; --loop)
			{
				rightp->m_kvlist[loop+kvpMoveFromLeft] = rightp->m_kvlist[loop];
			}

			// 父节点关键字移入右节点
			rightp->m_kvlist[kvpMoveFromLeft-1] = this->m_kvlist[leftchild];

			// 左节点关键字移入右节点
			for(int loop = 0; loop<kvpMoveFromLeft-1; ++loop)
			{
				rightp->m_kvlist[kvpMoveFromLeft-2-loop] = leftp->m_kvlist[leftp->m_keyNum-1-loop];
				leftp->m_kvlist[leftp->m_keyNum-1-loop] = NULL;
			}

			// 左节点关键字移入父节点
			this->m_kvlist[leftchild] = leftp->m_kvlist[leftp->m_keyNum - kvpMoveFromLeft];
			leftp->m_kvlist[leftp->m_keyNum - kvpMoveFromLeft] = NULL;

			if(!rightp->m_isLeaf)
			{
				//如果子节点不是叶子节点

				// 右节点准备加入kvpMoveFromLeft个子节点空间在子节点列表开头
				for(int loop=rightp->m_keyNum; loop>=0; --loop)
				{
					rightp->m_childlist[loop+kvpMoveFromLeft] = rightp->m_childlist[loop];
				}

				// 左节点子节点移入右节点
				for(int loop = 0; loop<kvpMoveFromLeft; ++loop)
				{
					rightp->m_childlist[kvpMoveFromLeft-1-loop] = leftp->m_childlist[leftp->m_keyNum-loop];
					leftp->m_childlist[leftp->m_keyNum-loop] = NULL;
				}
			}

			//更改左右子节点的关键数
			leftp->m_keyNum = mergeKeyNum/2;
			rightp->m_keyNum = rightp->m_keyNum + kvpMoveFromLeft;
		}
		else
		{
			//处于平衡状态，不用调整
		}
	}

	return true;
}

// 如果在以该节点为根的子树上找到有和keyval相同的值, 从树上删除找到的kvpair返回true；没有找到返回false
template<class BTRKT, class BTRVT>
struct jieningBtreeKVpair<BTRKT, BTRVT>* jieningBtree<BTRKT, BTRVT>::findToDeleteKV(const BTRKT& keyval, char* pathinf)
{
	bool needmerge = false;
	struct jieningBtreeKVpair<BTRKT, BTRVT>* rtnkvp = this->findToDeleteKV(keyval, needmerge);
	if(NULL == rtnkvp)
	{
		return NULL;
	}

	if(needmerge)
	{
		if(!this->m_isLeaf)
		{
			if(this->m_keyNum == 0)
			{
				struct jieningBtree<BTRKT, BTRVT>* thechild = this->m_childlist[0];
				this->m_childlist[0]  = NULL;
				if(NULL != thechild)
				{
					cout<<"thechild->m_keyNum="<<thechild->m_keyNum<<endl;
					cout<<"thechild->m_isLeaf="<<(thechild->m_isLeaf ? "true" : "false")<<endl;

					this->m_isLeaf = thechild->m_isLeaf;
					this->m_keyNum = thechild->m_keyNum;

					for(unsigned int loop = 0; loop < thechild->m_keyNum; ++loop)
					{
						this->m_kvlist[loop] = thechild->m_kvlist[loop];
						thechild->m_kvlist[loop] = NULL;
						if(!thechild->m_isLeaf)
						{
							this->m_childlist[loop] = thechild->m_childlist[loop];
							thechild->m_childlist[loop] = NULL;
						}
					}
					if(!thechild->m_isLeaf)
					{
						this->m_childlist[thechild->m_keyNum] = thechild->m_childlist[thechild->m_keyNum];
						thechild->m_childlist[thechild->m_keyNum] = NULL;
					}
					cout<<"this->m_keyNum="<<this->m_keyNum<<endl;
					cout<<"this->m_isLeaf="<<(this->m_isLeaf ? "true" : "false")<<endl;

					thechild->m_isLeaf = true;
					thechild->m_keyNum = 0;
					delete thechild;
				}
			}
		}
	}
	return rtnkvp;
}
template<class BTRKT, class BTRVT>
struct jieningBtreeKVpair<BTRKT, BTRVT>* jieningBtree<BTRKT, BTRVT>::findMinKvp()
{
	if(0 == this->m_keyNum)
	{
		return NULL;
	}
	if(this->m_isLeaf)
	{
		return this->m_kvlist[0];
	}
	else
	{
		return this->m_childlist[0]->findMinKvp();
	}
}

template<class BTRKT, class BTRVT>
struct jieningBtreeKVpair<BTRKT, BTRVT>* jieningBtree<BTRKT, BTRVT>::findMaxKvp()
{
	if(0 == this->m_keyNum)
	{
		return NULL;
	}
	if(this->m_isLeaf)
	{
		return this->m_kvlist[this->m_keyNum-1];
	}
	else
	{
		return this->m_childlist[this->m_keyNum]->findMaxKvp();
	}
}

template<class BTRKT, class BTRVT>
bool jieningBtree<BTRKT, BTRVT>::doTreeCheck()
{
	cout<<"in public jieningBtree::doTreeCheck"<<endl;
	int leaflevel=-1;
	bool rtn = this->doTreeCheck(true, NULL, NULL, leaflevel, 0);

	cout<<"in public jieningBtree::doTreeCheck, leaflevel="<<leaflevel<<", checkre="<<rtn<<endl;

	return rtn;
}

template<class BTRKT, class BTRVT>
bool jieningBtree<BTRKT, BTRVT>::doTreeCheck(bool isRoot, jieningBtreeKVpair<BTRKT, BTRVT>* lp, jieningBtreeKVpair<BTRKT, BTRVT>* rp, int& leaflevel, int nowlevel)
{
	cout<<((long)this)<<" in jieningBtree::doTreeCheck "<<endl;
	// m_keyNum 在[M/2-1, M-1]之间,根节点的m_keyNum在[1, M-1]
	if(this->m_keyNum >= this->m_maxChildNum)
	{
		cout<<"\tin jieningBtree::doTreeCheck, find this->m_keyNum >= this->m_maxChildNum"<<endl;
		return false;
	}
	if(this->m_keyNum < (this->m_maxChildNum/2-1))
	{
		if(!isRoot)
		{
			cout<<"\tin jieningBtree::doTreeCheck, find this->m_keyNum < (this->m_maxChildNum/2-1)"<<endl;
			return false;
		}
	}

	// kvlist检查
	for(unsigned int loop=0; loop < this->m_maxChildNum; ++loop)
	{
		if(loop < this->m_keyNum)
		{
			if(NULL == this->m_kvlist[loop])
			{
				cout<<"\tin jieningBtree::doTreeCheck, this->m_keyNum="<<this->m_keyNum<<", find NULL == this->m_kvlist["<<loop<<"]"<<endl;
				return false;
			}
			// key是按序排列的
			if(loop>0)
			{
				if(this->m_kvlist[loop]->thekey <= this->m_kvlist[loop-1]->thekey)
				{
					cout<<"\tin jieningBtree::doTreeCheck, this->m_kvlist["<<loop<<"] <= this->m_kvlist["<<(loop-1)<<"]"<<endl;
					return false;
				}
			}
			// 所有的key的值都比左父亲key值大
			if(NULL != lp)
			{
				if(lp->thekey >= this->m_kvlist[loop]->thekey)
				{
					cout<<"\tin jieningBtree::doTreeCheck, lp >= this->m_kvlist["<<loop<<"]"<<endl;
					return false;
				}
			}
			// 所有的key的值都比右父亲key值小
			if(NULL != rp)
			{
				if(rp->thekey <= this->m_kvlist[loop]->thekey)
				{
					cout<<"\tin jieningBtree::doTreeCheck, rp <= this->m_kvlist["<<loop<<"]"<<endl;
					return false;
				}
			}
		}
		else
		{
			if(NULL != this->m_kvlist[loop])
			{
				cout<<"\tin jieningBtree::doTreeCheck, this->m_keyNum="<<this->m_keyNum<<", find NULL != this->m_kvlist["<<loop<<"]"<<endl;
				return false;
			}
		}
	}

	// childlist检查
	if(this->m_isLeaf)
	{
		if(leaflevel < 0)
		{
			leaflevel = nowlevel;
		}
		if(leaflevel != nowlevel)
		{
			cout<<"\tin jieningBtree::doTreeCheck, leafnode, nowlevel="<<nowlevel<<", but leaflevel="<<leaflevel<<endl;
			return false;
		}

		for(unsigned int loop=0; loop < this->m_maxChildNum; ++loop)
		{
			if(NULL != this->m_childlist[loop])
			{
				cout<<"\tin jieningBtree::doTreeCheck, leafnode, but find NULL !=this->m_childlist["<<loop<<"]"<<endl;
				return false;
			}
		}
	}
	else
	{
		for(unsigned int loop=0; loop < this->m_maxChildNum; ++loop)
		{
			if(loop <= this->m_keyNum)
			{
				if(NULL == this->m_childlist[loop])
				{
					cout<<"\tin jieningBtree::doTreeCheck, this->m_keyNum="<<this->m_keyNum<<", but find NULL==this->m_childlist["<<loop<<"]"<<endl;
					return false;
				}
				bool childcheckre = this->m_childlist[loop]->doTreeCheck(
					false,
					(loop > 0 ? this->m_kvlist[loop-1] : NULL),
					(loop < this->m_keyNum ? this->m_kvlist[loop] : NULL),
					leaflevel,
					nowlevel+1);
				if(!childcheckre)
				{
					cout<<"\tin jieningBtree::doTreeCheck child["<<loop<<"] return false"<<endl;
					return false;
				}
			}
			else
			{
				if(NULL != this->m_childlist[loop])
				{
					cout<<"\tin jieningBtree::doTreeCheck, this->m_keyNum="<<this->m_keyNum<<", but find NULL!=this->m_childlist["<<loop<<"]"<<endl;
					return false;
				}
			}
		}
	}

	return true;
}

// 析构函数
template<class BTRKT, class BTRVT>
jieningBtree<BTRKT, BTRVT>::~jieningBtree()
{
	//cout<<((long)this)<<" in jieningBtree::~jieningBtree, keylist size="<<this->m_keyNum<<endl;
	//this->doPrint();
	for(unsigned int loop=0; loop<this->m_maxChildNum; ++loop)
	{
		if(loop < this->m_keyNum )
		{
			//cout<<((long)this)<<" loop="<<loop<<", key="<<this->m_keylist[loop]<<endl;
			if(NULL != this->m_kvlist[loop])
			{
				delete this->m_kvlist[loop];
				this->m_kvlist[loop] = NULL;
			}
		}
		if(NULL != this->m_childlist)
		{
			if(NULL != this->m_childlist[loop])
			{
				//cout<<((long)this)<<" in jieningBtree::~jieningBtree delete child loop="<<loop<<endl;
				delete this->m_childlist[loop];
				this->m_childlist[loop] = NULL;
			}
			if(NULL != this->m_childlist[loop+1])
			{
				//cout<<((long)this)<<" in jieningBtree::~jieningBtree delete child loop="<<loop<<endl;
				delete this->m_childlist[loop+1];
				this->m_childlist[loop+1] = NULL;
			}
		}
	}

	if(NULL != this->m_childlist)
	{
		//cout<<((long)this)<<" in jieningBtree::~jieningBtree delete this->m_childlist"<<endl;
		delete this->m_childlist;
		this->m_childlist = NULL;
	}

	if(NULL != this->m_kvlist)
	{
		//cout<<((long)this)<<" in jieningBtree::~jieningBtree delete this->m_keylist"<<endl;
		delete this->m_kvlist;
		this->m_kvlist = NULL;
	}
	this->m_keyNum = 0;
}
#endif
